#include <stdio.h>
#include <stdbool.h>

#define MAXSTRLEN 255 // 串的最大长度

typedef struct
{
    char ch[MAXSTRLEN + 1]; // 存储字符数组（0位置不使用）
    int length;             // 串的实际长度
} SString;

// 朴素模式匹配算法（Brute-Force）
int Index(SString S, SString T)
{
    /*
    返回子串T在主串S中的位置（从1开始计数）
    若不存在则返回0
    */
    if (T.length == 0)
        return 0; // 空串是任何串的子串

    int i = 1; // 主串指针
    int j = 1; // 子串指针

    while (i <= S.length && j <= T.length)
    {
        if (S.ch[i] == T.ch[j])
        {
            i++; // 继续比较后续字符
            j++;
        }
        else
        {
            i = i - j + 2; // i回溯到上次匹配开始位置的下一位
            j = 1;         // j重置为子串首字符
        }
    }

    if (j > T.length)
    {
        return i - T.length; // 匹配成功，返回位置
    }
    return 0; // 匹配失败
}

// 辅助函数：创建顺序串
bool StrAssign(SString &S, const char *chars)
{
    int len = 0;
    while (chars[len] != '\0' && len < MAXSTRLEN)
    {
        len++;
    }

    if (len == 0 || len > MAXSTRLEN)
        return false;

    for (int i = 1; i <= len; i++)
    {
        S.ch[i] = chars[i - 1];
    }
    S.length = len;
    return true;
}

// 打印串
void PrintString(SString S)
{
    for (int i = 1; i <= S.length; i++)
    {
        printf("%c", S.ch[i]);
    }
    printf("\n");
}

int main()
{
    SString S, T;

    // 测试用例1：正常匹配
    StrAssign(S, "ababcabcacbab");
    StrAssign(T, "abcac");
    printf("主串: ");
    PrintString(S); // ababcabcacbab
    printf("子串: ");
    PrintString(T);                          // abcac
    printf("匹配位置: %d\n\n", Index(S, T)); // 6

    // 测试用例2：不匹配
    StrAssign(S, "aaabbbccc");
    StrAssign(T, "aabbd");
    printf("主串: ");
    PrintString(S); // aaabbbccc
    printf("子串: ");
    PrintString(T);                          // aabbd
    printf("匹配位置: %d\n\n", Index(S, T)); // 0

    // 测试用例3：子串等于主串
    StrAssign(S, "hello");
    StrAssign(T, "hello");
    printf("主串: ");
    PrintString(S); // hello
    printf("子串: ");
    PrintString(T);                          // hello
    printf("匹配位置: %d\n\n", Index(S, T)); // 1

    // 测试用例4：子串为空串
    StrAssign(S, "anything");
    StrAssign(T, "");
    printf("主串: ");
    PrintString(S); // anything
    printf("子串: (空串)\n");
    printf("匹配位置: %d\n\n", Index(S, T)); // 0

    return 0;
}